package com.LeetCode.dp;

import org.junit.Test;

/**
 * 329. 矩阵中的最长递增路径
 */
public class LIP {

    int[][] matrix;

    int n, m;

    int[][] dp;

    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        this.n = matrix.length;
        this.m = matrix[0].length;
        this.dp = new int[n][m];
        this.matrix = matrix;
        int res = 0;
        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                res = Math.max(res, dfs(i,j));
            }
        }
        return res;
    }

    public int dfs(int i, int j){
        if(dp[i][j]!=0)
            return dp[i][j];

        dp[i][j]++;

        for(int[] dir : this.dirs){
            int nx = i + dir[0];
            int ny = j + dir[1];
            if(nx >= 0 && nx < this.n && ny >= 0 && ny < this.m && matrix[nx][ny] > matrix[i][j]){
                dp[i][j] = Math.max(dp[i][j], dfs(nx, ny) + 1);
            }
        }

        return dp[i][j];

    }


    @Test
    public void test(){
        int[][] matrix = {
                {9,9,4},
                {6,6,8},
                {2,1,1}
        };
        System.out.println(longestIncreasingPath(matrix));
    }
}
